package algorithm.graph.adjacencymatrix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;

public class Bellman {
    AdjacencyMatrixGraph graph;

    public Bellman(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }

    public void findPath(int from, int to, Consumer<int[]> onFind) {
        int[][] graphData = graph.getGraphData();
        int[] dist = new int[graph.getNodeCount()];
        int[] pre = new int[graph.getNodeCount()];
        Arrays.fill(dist, -1);
        Arrays.fill(pre, -1);
        dist[to] = 0;
        for (int i = 0; i < graph.getNodeCount(); i++) {
            for (int j = 0; j < graph.getNodeCount(); j++) {
                for (int k = 0; k < graphData[j].length; k++) {
                    if (graphData[j][k] > 0) {
                        if (dist[k] != -1) {
                            if (dist[j] == -1 || dist[k] + graphData[j][k] < dist[j]) {
                                dist[j] = dist[k] + 1;
                                pre[j] = k;
                            }
                        }
                    }
                }
            }
        }
        List<Integer> path = new ArrayList<>();
        if (dist[from] != -1) {
            int temp = from;
            while (pre[temp] != -1) {
                path.add(temp);
                temp = pre[temp];
            }
            path.add(to);
        }
        onFind.accept(path.stream().mapToInt(it -> it).toArray());
    }
}
